To solve minimum exposure path (MEP) problem in wireless sensor networks more efficiently, this work proposes an\nalgorithm called target guiding self-avoiding random walk with intersection (TGSARWI), which mimics the behavior of\na group of random walkers that seek path to their destinations in a strange area. Target guiding leads random walkers\nmove toward their end points, while self-avoiding prevents them from taking roundabout routes. Route intersections\nfurther accelerate the speed of seeking connected paths. Dijkstra algorithm (DA) is applied to solve MEP problem in a\nsub-network formed by multiple connected paths that walkers generate (called TGSARWI DA). Simulations show that\nthe path exposure found by TGSARWI DA is very close to that by DA in the global network (Global DA), whereas the\ntime complexity of computation is much lower. Compared with existing heuristic algorithms such as physarum optimization\nalgorithm (POA), our algorithm shows higher generality and efficiency. This algorithm also exhibits good robustness to the\nfluctuations of parameters. Our algorithm could be very useful for the solution to MEP problem in fields with large- or highdensity\nsensors.
Loading....